The invention pertains to the field of interleaving of bytes or symbols in streams of data to be transmitted as analog signals over noisy channels such as hybrid fiber coax of CATV systems, telephone lines, etc. More particularly, the invention pertains to a method for calculating block: depth in interleaving circuity more rapidly and with less expensive circuitry by eliminating an iterative divide step required by a first prior art method and by eliminating a multiplication step in a second prior art method.
Interleaving is a well known process of taking the contiguous bits or contiguous groups of bits called symbols from a byte and spreading them out in time for transmission. By spreading the bits or symbols of a byte over time over a noisy channel, and re-assembling the bits or symbols at the receiver, greater noise immunity can be achieved. Specifically, interleaving provides immunity to noise bursts which could otherwise wipe out an entire byte of data or several contiguous bytes.
Recently, a new type of modem called a cable modem has appeared on the market. As opposed to telephone modems which convert digital data to analog sound signals for transmission over telephone lines, cable modems convert digital data to radio frequency signals for transmission over hybrid fiber coaxial cable networks of cable TV systems. In the cable modem market, a new standard called DOCSIS has emerged which specifies certain aspects of cable modem designs for DOCSIS compliant cable modems.
The Institute of Electrical and Electronic Engineers (IEEE) has a working group which has recently proposed a high capacity physical layer specification for DOCSIS compliant cable modems. One of the upstream modes for such modems is a TDMA mode. This is a time division multiple access mode where bits from different channels or sources are transmitted upstream to the cable system head end during different timeslots. The bytes/symbols transmitted in each timeslot must be interleaved and this requires an interleaver circuit. Under the proposed methodology, bytes/symbols are transmitted to the interleaver in bursts from a Reed-Solomon encoder. These bursts are comprised of a series of codewords each of which has K bytes of payload and T error correction and detection bytes. Each bursts also has a burst profile transmitted therewith that includes data needed by the interleaver to calculate “block depth”.
Each block is a two dimensional array of multiple rows and columns of bytes or symbols. Interleaving is accomplished by writing bytes or symbols of the codewords into the blocks horizontally along the rows, but reading the bytes or symbols out of the blocks for transmission by column. This has the effect of interleaving the bytes or symbols by spreading them out over time. The codewords each have a width K+T which defines the width or number of bytes in each row of each block.
Sometimes the burst profile defines both the width and the depth of each block so there is no calculation for the interleaver to do. However, it also sometimes happens that the burst profile only specifies the width of each block and does not specify the depth, i.e., the number of rows in each block. In this case the interleaver circuit must calculate the number of rows in each block itself from the data it is given in the burst profile. The burst profile in this case will give only the block width in bytes or symbols and the maximum block size in bytes or symbols, the total number of bytes or symbols permitted in each block. This information, plus the length of the burst, i.e., the total number of bytes or symbols in the burst which is to be converted into blocks (each burst is different in size) is used by the interleaver to calculate the depth or number of rows in each block.
The goal is to try to get the number of rows in each block as close as possible to equal where the number of bytes or symbols in the burst is such that not all blocks can have the same number of rows. Making the blocks all approximately equal in depth gives all blocks approximately the same noise immunity.
The 802.14 Committee has proposed two prior art methods for calculating block depth in a DOCSIS compliant interleaver. The first method in the prior art differs from the second method in the prior art in that it involves an iterative divide step whereas the second method only has a one time divide step followed by a one time multiply step. The first method also differs from the second method in terms of where the short block occurs if not all blocks made from a burst have the same depth.
Prior art method 1 involves the following sequence of calculations. First, the total number of interleaver rows is calculated:ITOTO=CEIL(NP/NT)  (1) where    ITOTO=the total number of rows that can be made from a burst,    NP=the total burst: length in number of bytes or symbols; and    NT=the width or number of bytes or symbols in each row which also equals K+2T which is the length of the codeword output by the Reed-Solomon encoder; and where    CEIL is a mathematical operation of rounding up to the next integer if the result of the division is not a whole number.
Next, the maximum number of rows per block is calculated as follows:IT,MAX=FLOOR(BT/NT)  (2) where    IT,MAX=the maximum number of rows in each block;    BT=the maximum number of bytes or symbols in each block given by the burst profile;    NT=size of each row; and    FLOOR=is the mathematical operation of taking the next integer down if the result of the division is not a whole number.
Next, the method 1 calculation calculates the number of blocks that can be formed from the burst:NSO=CEIL(ITOTO/IT,MAX)  (3) where    ITOTO=the total number of rows that can be made from a burst; and    IT,MAX=the maximum number of rows per block.
Finally, an iterative calculation is made to calculate the depth IT(M) for each block where M is the block number in the series of blocks being formed:IT(M)=CEIL(ITOT(M-1 )/NS(M-1) for M=1,2, . . . , NS0  (4) where    ITOT(M-1)=the total number of rows left to be put in a block which have not been consumed in previous blocks; and    NS(M-1)=the number of blocks left to create
Step 5 is the iterative decrementing of the number of blocks left to create, calculated as follows:NS(M)=NS(M-1)−1  (5) 
Finally, step 6 is the iterative calculation of the number of rows left to be assigned to blocks after creation of the block whose depth was just calculated, which is calculated as:ITOT(M)=ITOT(M-1)−IT(M)  (6) 
The problem with this method 1 calculation is that it is slow because of the iterative divide required by equation (4). In other words, equation (4) must be calculated once for each block to be made from a burst. Divides are slow, and this slows the entire operation down.
Method 2 of the prior art does not involve an iterative divide, but is requires a divide followed by a multiply as both a divider and a multiplier are required. The calculation of method 2 is as follows. First, the total number of interleaver rows is calculated:ITOTO=CEIL(NF/NR)  (7) where    ITOTO is the total interleaver rows that can be made from a burst;    NF=the total number of bytes or symbols in a burst=NP in method 1; and    NR=the width in bytes or symbols of each row in each block.
Next in method 2, the maximum number of rows per block is calculated as follows:IR,MAX=FLOOR(Br/Nr)  (8) where    IR,MAX=the maximum number of rows per block;    Br=the maximum number of bytes or symbols in each block (from the burst profile);    Nr=the number of bytes or symbols in each row.
Next, the number of blocks is calculated as:NSO=CEIL(ITOTO/IR,MAX)  (9) where    NSO is the number of blocks that will be made from the burst;    ITOTO is the total number of rows that can be made from the burst; and    IR,MAX is the maximum number of rows per block.
Next in method 2, the depth or number of rows that will be in the first block is calculated by a one time divide as follows:IR1=FLOOR(ITOTO/NSO)  (10) where    IR1 is the number of rows in the first block;    ITOTO is the total number of interleaver rows that can be made from the burst; and    NSO is the number of blocks to be made from the burst.
Next in method 2, a one time multiply is performed to calculate the number of blocks with depth IR1 will be made as follows:M=NSO*(IR1+1)−ITOTO  (11) where    M is the number of blocks of depth IR1 that will be made; and    IR1=the depth of the first block; and    ITOTO is the total number of interleaver rows that can be made from the burst; and    NSO is the number of blocks to be made from the burst.
Finally, an iterative calculation is made from each block as follows:IR(i)=IR1, i=1, . . . , M IR1, i=M+1, . . . , NOS 
The problem with the method 2 calculation is that, although it does not require an iterative divide like method 1, it does require both a one time divide and a one time multiply. Therefore, both a divider and a multiplier are required.
Therefore, a need has arisen for a faster, more economical way of calculating depth of blocks in interleavers in general, and interleavers for DOCSIS compatible cable modems in particular.